public class Wu_4_23 {
    public static void main(String[] args) {
        
        // create students
        Student lilei = new Student("Li Lei", 1, "biology");
        Student hanmei = new Student("Han Mei", 2, "biology");
        Student minnie = new Student("Minnie", 3, "biology");
        Student jerry = new Student("Jerry", 4, "biology");
        Student mickey = new Student("Mickey", 5, "biology");
        Student tom = new Student("Tom", 6, "biology");

        // create TreeNode
        TreeNode Lilei = new TreeNode(lilei);
        TreeNode Hanmei = new TreeNode(hanmei);
        TreeNode Minnie = new TreeNode(minnie);
        TreeNode Jerry = new TreeNode(jerry);
        TreeNode Mickey = new TreeNode(mickey);
        TreeNode Tom = new TreeNode(tom);

        // insert the students into the BST
        new Wu_4_23().insert(Lilei, Hanmei);
        new Wu_4_23().insert(Lilei, Minnie);
        new Wu_4_23().insert(Lilei, Jerry);
        new Wu_4_23().insert(Lilei, Mickey);
        new Wu_4_23().insert(Lilei, Tom);

        // test the search function
        if (new Wu_4_23().search(Lilei, tom) != null)
            System.out.println(new Wu_4_23().search(Lilei, tom).key.getName());
        else
            System.out.println("null");
        // test the successor function
        System.out.println(new Wu_4_23().successor(Lilei).key.getName());

        // test the predecessor function
        System.out.println(new Wu_4_23().predecessor(Lilei).key.getName());

    }

    TreeNode predecessor(TreeNode x) {
        TreeNode y = null;
        if (x.left != null) {
            x = x.left;
            while (x != null) {
                y = x;
                x = x.right;
            }
            return y;
        } else {
            //否则找到第一个比它小的父节点
            while (x.key.compareTo(x.p.key) < 0) {
                x = x.p;
            }
            x = x.p;
            return x;
        }
    }

    TreeNode successor(TreeNode x) {
        TreeNode y = null;
        if (x.right != null) {
            x = x.right;
            while (x != null) {
                //出循环时，x==null（原因是多移动了一次）
                y = x;
                x = x.left;
            }
            return y;
        } else {
            //否则找到第一个比它大的父节点
            while (x.key.compareTo(x.p.key) > 0) {
                x = x.p;
            }
            x = x.p;
            return x;
        }
    }

    TreeNode search(TreeNode root, Student s) {
        TreeNode y = null;
        while (root != null) {
            y = root;
            if (s.compareTo(root.key) > 0) {
                root = root.right;
            } else if (s.compareTo(root.key) < 0) {
                root = root.left;
            } else {
                return y;
            }
        }
        return y;
    }

    void insert(TreeNode root, TreeNode s) {
        TreeNode y = null;
        // find proper position
        while (root != null) {
            y = root;
            if (s.key.compareTo(root.key) >= 0) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        // link
        //由于插入的元素始终位于叶子节点
        //无需像链表一样考虑，插入新元素时，要打断旧的连接
        if (s.key.compareTo(y.key) >= 0) {
            y.right = s;
        } else {
            y.left = s;
        }
        s.p = y;
    }

}

class TreeNode {
    Student key;
    TreeNode left;
    TreeNode right;
    TreeNode p;

    public TreeNode(Student key) {
        this.key = key;
        left = right = p = null;
    }
}

class Student implements Comparable<Student> {
    private String name;
    private int id;
    private String major;

    public Student(String name, int id, String major) {
        this.name = name;
        this.id = id;
        this.major = major;
    }

    // compare by name
    public int compareTo(Student s) {
        return this.name.compareTo(s.name);
    }

    public String getName() {
        return name;
    }
}